Learning optimally diverse rankings over large document collections.
Most learning to rank research has assumed that the utility of different documents is independent, which results in learned ranking functions that return redundant results. The few approaches that avoid this have rather unsatisfyingly lacked theoretical foundations, or do not scale. We present a learning-torank formulation that optimizes the fraction of satisfied users, with a scalable algorithm that explicitly takes document similarity and ranking context into account. We present theoretical justifications for this approach, as well as a near-optimal algorithm. Our evaluation adds optimizations that improve empirical performance, and shows that our algorithms learn orders of magnitude more quickly than previous approaches. 1.
Budget constrained auctions with heterogeneous items.

Ranking mechanisms in twitter%2Dlike forums.
We study the problem of designing a mechanism to rank items in forums by making use of the user reviews such as thumb and star ratings. We compare mechanisms where forum users rate individual posts and also mechanisms where the user is asked to perform a pairwise comparison and state which one is better. The main metric used to evaluate a mechanism is the ranking accuracy vs the cost of reviews, where the cost is measured as the average number of reviews used per post. We show that for many reasonable probability models, there is no thumb (or star) based ranking mechanism that can produce approximately accurate rankings with bounded number of reviews per item. On the other hand we provide a review mechanism based on pairwise comparisons which achieves approximate rankings with bounded cost. We have implemented a system, shoutvelocity [5], which is a twitter-like forum but items (i.e., tweets in Twitter) are rated by using comparisons. For each new item the user who posts the item is required to compare two previous entries. This ensures that over a sequence of n posts, we get at least n comparisons requiring one review per item on average. Our mechanism uses this sequence of comparisons to obtain a ranking estimate. It ensures that every item is reviewed at least once and winning entries are reviewed more often to obtain better estimates of top items.
A sketch%2Dbased distance oracle for web%2Dscale graphs.
We study the fundamental problem of computing distances between nodes in large graphs such as the web graph and social networks. Our objective is to be able to answer distance queries between pairs of nodes in real time. Since the standard shortest path algorithms are expensive, our approach moves the time-consuming shortest-path computation offline, and at query time only looks up precomputed values and performs simple and fast computations on these precomputed values. More specifically, during the offline phase we compute and store a small “sketch ” for each node in the graph, and at query-time we look up the sketches of the source and destination nodes and perform a simple computation using these two sketches to estimate the distance. Categories and Subject Descriptors G.2.2 [Graph Theory]: Graph algorithms, path and circuit problems
Revisiting the Examination Hypothesis with Query Specific Position Bias

Learning optimally diverse rankings over large document collections
Most learning to rank research has assumed that the utility of different documents is independent, which results in learned ranking functions that return redundant results. The few approaches that avoid this have rather unsatisfyingly lacked theoretical foundations, or do not scale. We present a learning-torank formulation that optimizes the fraction of satisfied users, with a scalable algorithm that explicitly takes document similarity and ranking context into account. We present theoretical justifications for this approach, as well as a near-optimal algorithm. Our evaluation adds optimizations that improve empirical performance, and shows that our algorithms learn orders of magnitude more quickly than previous approaches. 1.
Understanding Fashion Cycles as a Social Choice

Less is more sampling the neighborhood graph makes SALSA better and faster.
In this paper, we attempt to improve the effectiveness and the efficiency of query-dependent link-based ranking algorithms such as HITS, MAX and SALSA. All these ranking algorithms view the results of a query as nodes in the web graph, expand the result set to include neighboring nodes, and compute scores on the induced neighborhood graph. In previous work it was shown that SALSA in particular is substantially more effective than query-independent link-based ranking algorithms such as PageRank. In this work, we show that whittling down the neighborhood graph through consistent sampling of nodes and edges makes SALSA and its cousins both faster (more efficient) and better (more effective). We offer a hypothesis as to why “less is more”, i.e. why using a reduced graph improves performance.
Sparse Cut Projections in Graph Streams.
Abstract. Finding sparse cuts is an important tool for analyzing large graphs that arise in practice, such as the web graph, online social communities, and VLSI circuits. When dealing with such graphs having billions of nodes, it is often hard to visualize global partitions. While studies on sparse cuts have traditionally looked at cuts with respect to all the nodes in the graph, some recent works analyze graph properties projected onto a small subset of vertices that may be of interest in a given context, e.g., relevant documents to a query in a search engine. In this paper, we study how sparse cuts in a graph partition a certain subset of nodes. We call this partition a cut projection. We study the problem of finding cut projections in the streaming model that is appropriate in this context as the input graph is too large to store in main memory. Specifically, for a d-regular graph G on n nodes with a cut of conductance Φ and constant balance, we show how to parti-1 tion a randomly chosen set of k nodes in Õ( αΦ) passes over the graph stream and space Õ(nα + n3/4 k 1/4 αΦ 19/4), for any choice of α ≤ 1. The resulting partition is the projection of a cut of conductance of at most Õ(√Φ). We note that for k &lt; nα 6 Φ O(1) , this can be done in Õ(1/√αΦ) passes and space Õ(nα) that is sublinear in the number of nodes. 1
Less is more sampling the neighborhood graph makes SALSA better and faster.
In this paper, we attempt to improve the effectiveness and the efficiency of query-dependent link-based ranking algorithms such as HITS, MAX and SALSA. All these ranking algorithms view the results of a query as nodes in the web graph, expand the result set to include neighboring nodes, and compute scores on the induced neighborhood graph. In previous work it was shown that SALSA in particular is substantially more effective than query-independent link-based ranking algorithms such as PageRank. In this work, we show that whittling down the neighborhood graph through consistent sampling of nodes and edges makes SALSA and its cousins both faster (more efficient) and better (more effective). We offer a hypothesis as to why “less is more”, i.e. why using a reduced graph improves performance.
An axiomatic approach for result diversification.

Budget Constrained Auctions with Heterogeneous Items

An Axiomatic Framework for Result Diversification.
Informally speaking, diversification of search results refers to a trade-off between relevance and diversity in the set of results. In this article, we present a unifying framework for search result diversification using the axiomatic approach. The characterization provided by the axiomatic framework can help design and compare diversification systems, and we illustrate this using several examples. We also show that several diversification objectives can be reduced to the combinatorial optimization problem of facility dispersion. This reduction results in algorithms with provable guarantees for a number of well-known diversification objectives. 1
Bypass rates reducing query abandonment using negative inferences.

The power of two min%2Dhashes for similarity search among hierarchical data objects.
power of two min-hashes for similarity search among hierarchical
Estimating PageRank on graph streams.
This study focuses on computations on large graphs (e.g., the web-graph) where the edges of the graph are presented as a stream. The objective in the streaming model is to use small amount of memory (preferably sub-linear in the number of nodes n) and a few passes. In the streaming model, we show how to perform several graph computations including estimating the probability distribution after a random walk of length l, mixing time, and the conductance. We estimate the mixing time M of a random walk in Õ(nα+Mα √ q q Mn M n+) space and Õ( α α) passes. Furthermore, the relation between mixing time and conductance gives us an estimate for the conductance of the graph. By applying our algorithm for computing probability distribution on the web-graph, we can estimate the PageRank p of any node up to an additive error of √ ɛp in Õ( q M α) passes and Õ(min(nα + 1
Public Advertisement Broker Markets.

Exploiting asymmetry in hierarchical topic extraction.

A dictionary for approximate string search and longest prefix search.

Programmable clustering.
As network routers evolve towards supporting ever more higher-level networking functions beyond traditional network-layer and transport-layer protocols, programmability becomes a major design issue in network device OS (NDOS), which until very recently has been based on the type of OS used in embedded systems. On the other hand, it is now possible to build high-performance Internet routers from off-the-shelf PC-class hardware, particularly with the use of clustering technology. The goal of the Suez project is to build a cluster-based Internet router using generalpurpose processors as input/output link controllers and packet schedulers, and a Gigabit/sec system area network as the switching fabric. This paper presents the design and initial implementation of the Suez OS, which features scalable real-time packet scheduling, cache-conscious routing-table lookup, intra-cluster distributed buffer memory management, and a highly efficient kernel extension mechanism for active networking usin...
Exploiting anarchy in networks a game%2Dtheoretic approach to combining fairness and throughput.

Framework and algorithms for trend analysis in massive temporal data sets.

Framework and algorithms for trend analysis in massive temporal data sets.

A mechanism for equitable bandwidth allocation under QoS and budget constraints.

QoS Management in Educational Digital Library Environments.
Advances in multimedia computing technologies offer new approaches to the support of computerassisted education and training within many application domains. Novel interactive presentation tools can be built to enhance traditional teaching methods with more active learning. Since a variety of user expectations are possible in such an environment, research must address the incorporation of these factors into presentation tools. During an interactive learning/training process, presentation tools must be able to handle various types of delays. A flexibly adjustable quality of service (QoS) should thus be supported. In this paper, we investigate a framework and systematic strategies for supporting the continuous and synchronized retrieval and presentation of multimedia data streams in a client/server distributed multimedia environment for educational digital libraries. Specifically, we establish a practical framework for specifying multimedia objects, tasks, schedules, and synchronization ...
Buffer Model and Management in Distributed Multimedia Presentation Systems.

Buffer Management in Multimedia Database Systems.
The delivery of continuous and synchronous multimedia data from a database server to multiple destinations over a network presents new challenges in the area of buffer management. Many factors that were not considered in conventional buffer management must be examined. In this paper, we investigate the principles of buffer management for multimedia data presentations in object-oriented database environments. The primary goal is to minimize the response time of multimedia presentations while ensuring that all continuity and synchronization requirements are satisfied. Minimum buffering requirements to guarantee the continuity and synchrony of the presentation of multimedia data are first proposed. A prefetching technique which satisfies these requirements is then developed. These principles and technique provide users with the full range of information required to develop a database environment for multimedia presentations. 1 Introduction  Advances in multimedia computing technologies ha...
NetMedia A Client%2DServer Distributed Multimedia Environment.

